package demo;

public class Tree<E> {
    private Node<E> root;
    private int size;

    private static class Node<E>{
        E item;
        Node<E> left;
        Node<E> right;
        public Node(E e){
            item = e;
        }
        public boolean add(E e){ //item=680  e=520
            //先比较大小，如果小就添加到左侧，大了添加到右侧
            //item 代表当前根元素中的数， e代表需要添加的数据
            if (! (e instanceof Comparable)){
                throw new RuntimeException("不能比较大小");
            }
            Comparable value=(Comparable)e;
            int result = value.compareTo(item);
            if (result==0){ //数据相等
                //数据相等 返回 false 表示添加失败。
                return false;
            }else if(result>0){ //e 大于当前的 item
                //添加到右侧 e = 800
                if(right == null){
                    right = new Node<E>(e); //780
                    return true;
                }else{ // 右侧已经有节点了, 将右侧看着一个完整树将e添加到右侧
                    return right.add(e);
                }
            }else {// e 小于当前的 item
                //添加到左侧
                if (left == null){
                    left = new Node<>(e);
                    return true;
                }else{ // 左侧已经有节点了, 将左侧看着一个完整树将e添加到左侧
                    return left.add(e);
                }
            }
        }

        public void appendTo(StringBuilder buf) {
            //buf 是在toString方法中创建的对象，需要返回的数据
            //添加到buf中即可。
            //添加顺序： 左left， 中item  右right
            if(left != null){
                //添加左
                left.appendTo(buf);
            }
            //添加中item
            buf.append(item).append(", ");
            if(right != null){
                //添加右
                right.appendTo(buf);
            }
        }
    }
    /**
     * 将元素e添加到二叉树中
     * 如果元素相同，就添加失败
     * @param e 被添加元素
     * @return 添加成功返回true
     */
    public boolean add(E e){
        if (root==null){
            root = new Node<>(e);
            size++;
            return true;
        }
        //有根元素了, 将数据添加到根元素中
        //由根元素比较大小，决定如何处理数据
        //如果添加成功，就返回true，否则返回false
        boolean added = root.add(e);
        if(added){
            size++;
        }
        return added;
    }

    @Override
    public String toString() {
        if (root==null){
            return "[]";
        }
        //[560, 680, 980]
        StringBuilder buf = new StringBuilder("[");
        //将根元素中的数据，添加到 buf 中
        root.appendTo(buf);
        buf.delete(buf.length()-2, buf.length());
        return buf.append("]").toString();
    }
}
